#pragma once
#include<iostream>
using namespace std;
#include<assert.h>


template <class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_bf(0)
	{}
};

template <class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	AVLTree() = default;

	AVLTree(const AVLTree<K, V>& kv)
	{
		_root = Copy(kv._root);
	}

	AVLTree<K, V>& operator=(AVLTree<K, V> kv)
	{
		swap(_root, kv._root);
		return *this;
	}

	~AVLTree()
	{
		_Destory(_root);
		_root = nullptr;
	}

	bool Insert(const pair<K, V>& kv)
	{
		// 如果树为空就直接插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		// cur用来寻找插入的位置
		// parent用来记录cur的父节点
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			// 如果key大于当前节点就往右走
			// 如果key小于当前节点就往左走
			// 如果相等则不插入 返回
			if (kv.first < cur->_kv.first)// 小于
			{
				parent = cur; // 更新父节点
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)// 大于
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false; // 表示该点已经存在
			}
		}
		// 到此找到了插入的位置
		// 父节点的位置也定了下来
		// 判断cur是父节点的左孩子还是右孩子
		cur = new Node(kv);
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;// 链接新节点和父节点

		// 更新平衡因子
		while (parent)
		{
			if (cur == parent->_left)
				parent->_bf--;
			else
				parent->_bf++;

			// 更新后的平衡因子分为这几种情况：
			// 1. 0 -- 代表插入前平衡因子为 1/-1 不用管
			// 2. 1/-1 -- 代表插入前平衡因子为 0 不用管
			// 3. 2/-2 -- 代表插入前平衡因子为 1/-1 需要旋转
			// 4. 大于2或小于-2 报错
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 继续向上更新
				cur = parent;
				parent = cur->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 旋转
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					// 都是右树高  左旋
					//RotateL(parent);
					myRotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					// 都是左树高  右旋
					//RotateR(parent);
					myRotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					// 异号
					// 左高 后 右高
					// 先左旋后右旋
					RotateLR(parent);
				}
				else // (parent->_bf == 2 && cur->_bf == -1)
				{
					// 异号
					// 右高 后 左高
					// 先右旋后左旋
					RotateRL(parent);
				}
				break; // 难道是这里的问题导致subRL为nullptr？  少了个break
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	bool Erase(const K& key)
	{
		if (_root == nullptr)
		{
			return false;
		}

		Node* cur = _root;
		Node* parent = nullptr;

		// 先找到这个数
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// 找到了 开始删除
				if (cur->_left == nullptr)// 如果左孩子为空
				{
					if (parent == nullptr) // 如果删除的是根节点
					{
						_root = _root->_right;
					}
					// 判断cur是parent的左右孩子
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}

						delete cur;
						return true;
					}
				}
				else if (cur->_right == nullptr)// 如果右孩子为空
				{
					if (parent == nullptr) // 如果删除的是根节点
					{
						_root = _root->_left;
					}
					else
					{
						// 判断cur是parent的左右孩子
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}

						delete cur;
						return true;
					}
				}
				// 前两个就包括了 0-1 个孩子的情况
				else // 这个就是有两个孩子的情况
				{
					// 如果有两个孩子 就得找到一个现有的节点换到被删节点的位置做替换
					// 这个节点通常是左子树的最大节点或右子树的最小节点
					// 从右子树中找到最小的孩子
					Node* rightMin = cur->_right;
					Node* rightMinP = cur;

					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}

					// 至此找到了最小的节点
					cur->_key = rightMin->_key;

					if (rightMin == rightMinP->_left)
						rightMinP->_left = rightMinP->_right;
					else
						rightMinP->_right = rightMinP->_right;

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}

	// 打印
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	void _Destory(Node* root)
	{
		if (root == nullptr)
			return;

		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newRoot = new Node(root->_key, root->_value);
		newRoot->_left = root->_left;
		newRoot->_right = root->_right;

		return newRoot;
	}

	/*void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* parentParent = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}

		parent->_bf = subR->_bf = 0;
	}*/
	// copy
	/*void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* parentParent = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}

		parent->_bf = subR->_bf = 0;
	}*/


	void myRotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		/*if (subRL)
			parent->_right = subRL;

		subRL->_parent = parent;*/

		if (subRL)
			subRL->_parent = parent;
		
		parent->_right = subRL;
		
		Node* parentParent = parent->_parent;
		parent->_parent = subR;
		subR->_left = parent;

		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}

		// 更新平衡因子
		parent->_bf = subR->_bf = 0;
	}

	/*void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (parentParent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}

		parent->_bf = subL->_bf = 0;
	}*/
	// copy
	/*void  RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parentParent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}
	}*/

	void myRotateR(Node* parent) // 节点插入在了左树 右旋满足的条件是左数高于右树
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		if (subLR)
			subLR->_parent = parent; // 如果subLR存在 链接

		subL->_right = parent;
		parent->_left = subLR;

		Node* parentParent = parent->_parent; // 记录parent的父节点
		parent->_parent = subL; // 链接

		if (parentParent == nullptr)
		{
			// 代表parent是根节点
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			//// 链接parent的父节点
			//subL->_parent = parentParent;

			// 判断是左树还是右树
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}

		// 更新平衡因子
		parent->_bf = subL->_bf = 0;
	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		/*RotateL(parent->_left);
		RotateR(parent);*/
		myRotateL(parent->_left);
		myRotateR(parent);

		// 更新平衡因子
		if (bf == 0)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else
		{
			assert(false);
		}
	}


	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		/*RotateR(parent->_right);
		RotateL(parent);*/
		myRotateR(parent->_right);
		myRotateL(parent);

		// 更新平衡因子
		if (bf == 0)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subR->_bf = -1;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 1;
		}
		else
		{
			assert(false);
		}
	}
	// copy
	//void RotateRL(Node* parent)
	//{
	//	Node* subR = parent->_right;
	//	Node* subRL = subR->_left;
	//	int bf = subRL->_bf; // 26有问题

	//	RotateR(parent->_right);
	//	RotateL(parent);

	//	if (bf == 0)
	//	{
	//		subR->_bf = 0;
	//		subRL->_bf = 0;
	//		parent->_bf = 0;
	//	}
	//	else if (bf == 1)
	//	{
	//		subR->_bf = 0;
	//		subRL->_bf = 0;
	//		parent->_bf = -1;
	//	}
	//	else if (bf == -1)
	//	{
	//		subR->_bf = 1;
	//		subRL->_bf = 0;
	//		parent->_bf = 0;
	//	}
	//	else
	//	{
	//		assert(false);
	//	}
	//}

private:
	Node* _root = nullptr;
};



void TestAVLTree()
{
	AVLTree<int, int> t;
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

	for (auto e : a)
	{
		t.Insert({ e,e });
	}

	t.InOrder();
}
